1. Technical Field
The present invention pertains to communication systems. In particular, the present invention pertains to a communication system employing broadcast-based flooding schemes for synchronizing routing databases with reduced communication protocol overhead.
2. Discussion of Related Art
Generally, wireless networks maybe arranged in a two-tier architecture similar to that of conventional cellular telephone systems. The first tier typically includes clusters or cells each including a plurality of communication nodes or cluster members. One node within each cluster is designated as a cluster head or base station. The second tier includes a backbone network formed of the cluster head nodes to enable communications between different clusters (e.g., for data transmitted over greater distances). The formation of clusters and designation of cluster head nodes is generally performed dynamically and in accordance with an intranet protocol (e.g., a protocol for communications within the two-tier network) that further performs routing functions within the network. The intranet protocol is preferably a link-state type of routing protocol that is implemented on the backbone network. The cluster head nodes each include a database that is synchronized with other cluster head node databases by transference of Link- State Advertisement (LSA) packets in accordance with the protocol. These databases include information enabling the cluster head nodes to determine appropriate paths for routing messages through the network, while the LSA packets provide information to update the databases.
In order to facilitate internet routing or routing between the two-tier and other external networks (e.g., the Internet), a modified version of the conventional Open Shortest Path First (OSPF) Protocol is employed. The OSPF protocol is basically a routing protocol employed for Internet Protocol (IP) type networks, while the modified protocol or Radio Open Shortest Path First (ROSPF) protocol is similar to OSPF, but is adapted for use with radio or wireless networks. For examples of implementation of the OSPF Protocol, reference is made to RFC 1583, Moy, xe2x80x9cOSPF Version 2,xe2x80x9d March 1994, the disclosure of which is incorporated herein by reference in its entirety. Thus, the ROSPF protocol is basically an internetworking or gateway protocol facilitating communications with external networks.
Routing is accomplished in the OSPF protocol by each network node having a routing database containing information related to network topology (e.g., links between network nodes). The routing database is utilized by each node to determine a path for transmitting a message to a destination site. The routing databases are updated by exchanging Link-State Advertisement (LSA) packets between neighboring nodes. These packets generally include information related to current links of network nodes and are typically transferred periodically and/or in the event of a modification to the network topology. The OSPF protocol designates a particular router to flood LSA packets to neighbors in broadcast type networks, while LSA packets are transmitted via point-to-point and/or broadcast packets within non-broadcast type networks. The ROSPF protocol employed by the two-tier network described above is similar to the OSPF protocol and exchanges LSA type packets between neighbors (e.g., cluster head and member nodes) to synchronize routing databases as described above. Since the two-tier network is not a broadcast type network, an LSA packet is sent as a point-to-point message to each of its protocol neighbors.
The above-described technique for transmitting LSA packets on the two-tier network suffers from several disadvantages. In particular, the intranet and ROSPF protocols generate control traffic where the amount of traffic increases with network size. In fact, the amount of ROSPF overhead traffic increases at a significantly greater rate than network capacity as network size increases, thereby degrading network performance. Although the ROSPF protocol introduces additional overhead in initializing neighbors and exchanging database descriptions, the predominant portion of the overhead is attributed to the flooding or transmission of LSA packets. As a result of the rate of increased overhead, the network becomes unsuitable to transport user traffic or maintain a functioning state when the network includes greater than approximately one-hundred fifty nodes. Since the two-tier network may employ a maximum of approximately one-thousand nodes, the increased overhead limits performance of small-scale networks and restricts deployment of the protocol for large-scale networks.
The present invention overcomes the aforementioned problems and achieves transmission of LSA type or database update packets for synchronization of node routing databases with a reduced rate of overhead increase in relation to network size. This is accomplished by inserting the ROSPF protocol database update packets within intranet protocol beacon type or node status packets to reduce the rate of protocol overhead. The node status packets are periodically transmitted by cluster member and cluster head nodes to advertise the presence of that node to the network. The present invention minimizes the impact of protocol overhead on network throughput, and permits an ROSPF type protocol to be utilized on large-scale wireless networks. Thus, networks may employ the protocol, while scaling to a greater size.
Accordingly, it is an object of the present invention to reduce the rate of overhead of a communication routing protocol and enable employment of the protocol with large-scale type networks.
It is another object of the present invention to transmit database update packets of a communication protocol within packets of other protocols to reduce communication protocol overhead and enhance communication network throughput.
Yet another object of the present invention is to synchronize routing databases of communication network nodes in a manner that minimally affects network throughput.
The aforesaid objects may be achieved individually and/or in combination, and it is not intended that the present invention be construed as requiring two or more of the objects to be combined unless expressly required by the claims attached hereto.
According to the present invention, Link-State Advertisement (LSA) type or database update messages or packets of an internetworking protocol are transmitted within a wireless communication system or network via insertion of the packet within packets of an intranet protocol. Specifically, a wireless network includes a plurality of nodes arranged into clusters with each cluster having cluster member nodes and a designated cluster head node. The nodes communicate with each other via an intranet protocol, while the network may communicate with other external networks in accordance with an internetworking protocol (e.g., a modified version of the conventional Open Shortest Path First (OSPF) routing protocol, or a Radio Open Shortest Path First (ROSPF) protocol). A database within each network node contains link information for that node, while the ROSPF LSA type packets contain information to update the node databases. The ROSPF LSA type packets are transmitted to neighbors of each node to enable each database to maintain current information. In order to reduce overhead of transmitting numerous LSA type packets, the present invention transmits the ROSPF LSA type packet within an intranet protocol beacon type or node status packet that is periodically broadcasted within the network. Thus, the overhead rate of increase is reduced, thereby permitting the network to utilize an ROSPF type protocol while expanding to larger scales.
The above and still further objects, features and advantages of the present invention will become apparent upon consideration of the following detailed description of specific embodiments thereof, particularly when taken in conjunction with the accompanying drawings wherein like reference numerals in the various figures are utilized to designate like components.